//a_mem.cpp
//

template <typename T>
T ** (Add_Row) (T **ps, int size, int col)
{
		T ** tmp = new T * [size+1];
		for (int i= 0; i< size; ++i)
		{
			tmp[i] = ps[i];
		}
		tmp[size] = new T [col];
		delete [] ps;
		return tmp;
}

template <typename T>
int Insert_Col
	(
		T **(& arr),
		size_t *(& index_col),
		const size_t insert_pos,
		const size_t row,
		size_t & col,
		T symbol
	)
//	0 - недостатньо пам"яті
//	1 - успішне виконання функції
{
	size_t capacity = col + 1;

	size_t * index_tmp = new size_t [capacity];
	if (index_tmp==NULL) return 0;
	
	for (size_t i= 0; i< col; ++i) { index_tmp[i] = index_col[i]; }
	index_tmp[col] = col;
	delete [] index_col;
	index_col = index_tmp;
	
	for (size_t i= 0; i< row; ++i)
	{
		T * tmp_line = new T [capacity];
		if (tmp_line==NULL) return 0;
		for (size_t j= 0; j< col; ++j)
		{
			tmp_line[j] = arr[i][j];
		}
		tmp_line[col]=symbol;
		delete [] arr[i];
		arr[i] = tmp_line;
	}
	col= capacity;
	int ofset = -1*(capacity - insert_pos);
	
	Move_Line (index_col, capacity, ofset, capacity);
	return 1;
}

template <typename T>
int Insert_Row
	(
		T **(& arr),
		const size_t *(index_col),
		const size_t insert_pos,
		size_t & row,
		const size_t col,
		T symbol
	)
	//	0 - недостатньо пам"яті
	//	1 - успішне виконання функції
{
	size_t capacity = row + 1;

	T ** index_arr = new T * [capacity];
	if (index_arr==NULL) return 0;
	
	for (size_t i= 0; i< row; ++i) { index_arr[i] = arr[i]; }
	index_arr[row] = new T [col];
	if (index_arr[row]==NULL) return 0;
	delete [] arr;
	arr = index_arr;
	for (size_t k= 0; k< col; ++k)
		arr[row][index_col[k]] = symbol;
	
	row= capacity;
	int ofset = -1*(capacity - insert_pos);
	
	Move_Line (arr, capacity, ofset, capacity);
	return 1;
}

template <typename T>
int Move_Line
	(
		T * index_col,			//індексний масив
		const size_t position,	//позиція об"єкта
		const signed int ofset,	//зміщення (+/-) відносно позиції
		const size_t capacity	//ємність матриці у відповідному напрямку
	)
	//Переміщення стрічки або стовбця не рівноміної динамічної матриці
	//	0 - позиція або ціль виходять за межі існуючої матриці
	//	1 - переміщення виконано успішно
{
	signed int target = position + ofset;
	if ((position <= 0)||(position > capacity)||(target <= 0 )||(target > capacity)) return 0;
	
	size_t ind_pos = position - 1;
	T tmp_pos = index_col[ind_pos];
	
	if (ofset < 0)
	{
		for(size_t i= ind_pos; i>= target; --i)
		{
			index_col[i] = index_col[i-1];
		}
	}
	
	if (ofset > 0)
	{
		for(size_t i= ind_pos; i< target-1; ++i)
		{
		
			index_col[i] = index_col[i+1];
		}
	}
	index_col[target-1] = tmp_pos;
	return 1;
}

template <typename T>
int Move_Line_Cycle
	(
		T * index_col,			//індексний масив
		int position,	//позиція об"єкта
		int step,			//зміщення (+/-) відносно позиції
		const size_t capacity	//ємність матриці у відповідному напрямку
	)
	//Переміщення стрічки або стовбця не рівноміної динамічної матриці
	//	0 - позиція або ціль виходять за межі існуючої матриці
	//	1 - переміщення виконано успішно
{
	//signed int target = position + ofset;
	if ((position <= 0)||(position > capacity)) return 0;
	// if (position < 0) position *= -1;	//
	// position %= capacity;				//Захист від помилкової позиції елементу
	
	int i = position-1;
	int i_next = position-1;
	T tmp_pos = index_col[i];
	
	//Два цикли з однаковими умовами для більшої швидкодії
	if (step < 0)
	{
		step *= -1;
		for(int n= position; n< step; ++n)
		{
			i = capacity - ((n+1)%capacity) - 1;
			i_next = capacity - ((n+2)%capacity) - 1;
			index_col[i] = index_col[i_next];
		}
	}
	
	if (step > 0)
	{
		for(int n= position; n< step; ++n)
		{
			i = (position-1 + step) % capacity;
			i_next = (position + step) % capacity;
			index_col[i] = index_col[i_next];
		}
	}

	index_col[i_next] = tmp_pos;
	return 1;
}



template <typename T>
int Create_Table (T ** (&arr), size_t *(&index_col), size_t row, size_t col)
//Створення динамічної матриці N x M та індексного масиву для стовбців
{
	index_col = new size_t [col];
	if (index_col==NULL) return 0;
	for (size_t i= 0; i< col; ++i) index_col[i] = i;
	
	arr = new T * [row];
	if (arr==NULL) return 0;
	for (size_t i= 0; i< row; ++i) 
	{
		arr[i] = new T [col];
		if (arr[i]==NULL) return 0;
	}
	return 1;
}




